package lists

// list容器的增强版，增加筛选过滤、反转、判断条件、遍历执行等方法
// 返回一个 *List 的方法，才会修改自身，其他返回值的不会，并且，
// Map 和 Sublist 是返回新的一个 *List 。

import (
	"bytes"
	"container/list"
	"encoding/gob"
	"fmt"
	"reflect"
	"strconv"
	"strings"
)

func init() {

}

type List struct {
	list.List
}

type CompareFunc func(e1 interface{}, e2 interface{}) bool
type FilterFunc func(e interface{}) bool
type FoldFunc func(e interface{}, acc interface{}) interface{}
type ForeachFunc func(v interface{})
type MapFunc func(v interface{}) interface{}

// 将任意类型的数据转换成字节数组
func GetBytes(key interface{}) []byte {
	var buf bytes.Buffer
	enc := gob.NewEncoder(&buf)
	err := enc.Encode(key)
	if err != nil {
		return nil
	}
	return buf.Bytes()
}

// 创建包含参数的列表，支持任意个任意类型的参数：
//	l := NewList2(1, "2", 3, NewList2(4, 5))
func New(vals ...interface{}) *List {
	l := new(List)
	for _, val := range vals {
		l.PushBack(val)
	}
	return l
}

// 从一个列表复制一个新的列表
func Copy(l1 *List) *List {
	l := new(List)
	l.PushBackList(&l1.List)
	return l
}

// 创建一个由 N 个元素 v 组成的列表：
//	l := Duplicate(5, 1)  // 结果为： [1 1 1 1 1]
func Duplicate(N int, v interface{}) *List {
	l := new(List)
	for i := 0; i < N; i++ {
		l.PushBack(v)
	}
	return l
}

// 生成一个由 From 到 To，递增值是 Incr 的序列正数列表，From、To可以是负数：
//	l := Sequence(0, 6, 2)  // 结果为： [0 2 4 6]
func Sequence(From int, To int, Incr int) *List {
	l := new(List)
	for i := From; (Incr > 0 && i <= To) || (Incr < 0 && i >= To); i += Incr {
		l.PushBack(i)
	}
	return l
}

func CompareDefaultFunc(e1 interface{}, e2 interface{}) bool {
	switch v1 := e1.(type) {
	case int:
		v2, ok2 := e2.(int)
		if !ok2 {
			return bytes.Compare(GetBytes(e1), GetBytes(e2)) < 0
		}
		return v1 < v2
	case string:
		v2, ok2 := e2.(string)
		if !ok2 {
			return bytes.Compare(GetBytes(e1), GetBytes(e2)) < 0
		}
		return strings.Compare(v1, v2) < 0
	default:
		return bytes.Compare(GetBytes(e1), GetBytes(e2)) < 0
	}
}

// 格式化列表的字段输出字符串
// bool 输出 true 或者 false，int 直接输出，float 最大小数 6 位，
// List2列表使用 < > 括号，其他类型使用 { } 括号；
// 指针前面加 &
func (l *List) String() string {
	var out bytes.Buffer
	out.WriteString("<")
	for p := l.Front(); p != nil; p = p.Next() {
		if p != l.Front() {
			out.WriteString(" ")
		}
		switch v := p.Value.(type) {
		case bool:
			if !v {
				out.WriteString("false")
			} else {
				out.WriteString("true")
			}
		case nil:
			out.WriteString("nil")
		case int:
			out.WriteString(strconv.Itoa(v))
		case float32:
			out.WriteString(strconv.FormatFloat(float64(v), 'g', 6, 32))
		case float64:
			out.WriteString(strconv.FormatFloat(v, 'g', 6, 64))
		case string:
			out.WriteString("\"")
			out.WriteString(v)
			out.WriteString("\"")
		case *List:
			out.WriteString("&")
			out.WriteString(v.String())
		case List:
			out.WriteString(v.String())
		default:
			typeOf := reflect.TypeOf(p.Value)
			if typeOf.Kind().String() == "ptr" {
				out.WriteString("&")
				typeOf = typeOf.Elem()
			}
			out.WriteString("{")
			if typeOf.Name() == "" {
				out.WriteString(typeOf.Kind().String())
			} else {
				out.WriteString(typeOf.Name())
			}
			out.WriteString("}")
		}
	}
	out.WriteString(">")
	return out.String()
}

// 判断列表里的所有元素是否都满足条件
func (l *List) All(f FilterFunc) bool {
	for p := l.Front(); p != nil; p = p.Next() {
		if !f(p.Value) {
			return false
		}
	}
	return true
}

// 判断列表里的是否存在某一个元素满足条件
func (l *List) Any(f FilterFunc) bool {
	for p := l.Front(); p != nil; p = p.Next() {
		if f(p.Value) {
			return true
		}
	}
	return false
}

// 添加另一列表的所有元素到列表的最后
func (l *List) Append(l2 *List) *List {
	l.PushBackList(&l2.List)
	return l
}

// 删除列表的一个元素
func (l *List) Delete(v interface{}) *List {
	for p := l.Front(); p != nil; p = p.Next() {
		if p.Value == v {
			l.Remove(p)
			break
		}
	}
	return l
}

// 删除列表的所有值等于 v 的元素
func (l *List) DeleteAll(v interface{}) *List {
	for p := l.Front(); p != nil; {
		pnext := p.Next()
		if p.Value == v {
			l.Remove(p)
		}
		p = pnext
	}
	return l
}

// 从头到尾依次删除满足条件的元素，直到遇到不满足条件的元素为止。
func (l *List) DropWhile(f FilterFunc) *List {
	for p := l.Front(); p != nil; {
		pnext := p.Next()
		if f(p.Value) {
			l.Remove(p)
		} else {
			break
		}
		p = pnext
	}
	return l
}

// 保留满足条件的元素，删除不满足条件的元素。
func (l *List) Filter(f FilterFunc) *List {
	for p := l.Front(); p != nil; {
		pnext := p.Next()
		if !f(p.Value) {
			l.Remove(p)
		}
		p = pnext
	}
	return l
}

// 返回第一个元素
func (l *List) First() interface{} {
	if l.Front() == nil {
		return nil
	}
	return l.Front().Value
}

// 将多层嵌套列表转为单层列表
func (l *List) Flatten() *List {
	needAgain := false
	for p := l.Front(); p != nil; {
		pnext := p.Next()
		switch v := p.Value.(type) {
		case List:
			needAgain = true
			for p2 := v.Front(); p2 != nil; p2 = p2.Next() {
				l.InsertBefore(p2.Value, p)
			}
			l.Remove(p)
		case *List:
			needAgain = true
			for p2 := v.Front(); p2 != nil; p2 = p2.Next() {
				l.InsertBefore(p2.Value, p)
			}
			l.Remove(p)
		}
		p = pnext
	}
	if needAgain {
		return l.Flatten()
	}
	return l
}

// 从头到尾依次对所有元素递归调用函数 f，并将累计结果 acc 返回。
func (l *List) FoldL(f FoldFunc, acc interface{}) interface{} {
	for p := l.Front(); p != nil; p = p.Next() {
		acc = f(p.Value, acc)
	}
	return acc
}

// 从尾到头依次对所有元素递归调用函数 f，并将累计结果 acc 返回。
func (l *List) FoldR(f FoldFunc, acc interface{}) interface{} {
	for p := l.Back(); p != nil; p = p.Prev() {
		acc = f(p.Value, acc)
	}
	return acc
}

// 从头到尾依次对所有元素执行函数 f。
func (l *List) Foreach(f ForeachFunc) {
	for p := l.Front(); p != nil; p = p.Next() {
		f(p.Value)
	}
}

// 判断是否与另一个列表拥有相同的元素
func (l *List) IsEqual(l2 *List) bool {
	p1 := l.Front()
	p2 := l2.Front()
	for p1 != nil && p2 != nil {
		if p1.Value != p2.Value {
			return false
		}
		p1 = p1.Next()
		p2 = p2.Next()
	}
	return p1 == nil && p2 == nil
}

// 返回最后一个元素
func (l *List) Last() interface{} {
	if l.Back() == nil {
		return nil
	}
	return l.Back().Value
}

func (l *List) Map(f MapFunc) *List {
	l2 := New()
	for p := l.Front(); p != nil; p = p.Next() {
		l2.PushBack(f(p.Value))
	}
	return l2
}

// 返回数值最大的一个元素
func (l *List) Max() interface{} {
	now := l.Front()
	for p := l.Front(); p != nil; p = p.Next() {
		if !CompareDefaultFunc(p, now) {
			now = p
		}
	}
	return now.Value
}

// 判断 v 是否存在列表中
func (l *List) Member(v interface{}) bool {
	for p := l.Front(); p != nil; p = p.Next() {
		if p.Value == v {
			return true
		}
	}
	return false
}

// 返回数值最小的一个元素
func (l *List) Min() interface{} {
	now := l.Front()
	for p := l.Front(); p != nil; p = p.Next() {
		if CompareDefaultFunc(p, now) {
			now = p
		}
	}
	return now.Value
}

// 取第N个元素，0 为第一个，正数从头开始，负数从尾开始
func (l *List) Nth(i int) interface{} {
	if i >= 0 {
		j := 0
		for p := l.Front(); p != nil && j <= i; p = p.Next() {
			if j == i {
				return p.Value
			}
			j++
		}
	} else {
		j := -1
		for p := l.Back(); p != nil && j <= i; p = p.Prev() {
			if j == i {
				return p.Value
			}
			j--
		}
	}
	return nil
}

// 根据条件将列表里的元素分成满足条件的和不满足条件的
func (l *List) Partition(f FilterFunc) (*List, *List) {
	l1 := New()
	l2 := New()
	for p := l.Front(); p != nil; p = p.Next() {
		if f(p.Value) {
			l1.PushBack(p.Value)
		} else {
			l2.PushBack(p.Value)
		}
	}
	return l1, l2
}

// 反转列表的元素
func (l *List) Reverse() *List {
	for p := l.Front(); p != nil; {
		pnext := p.Next()
		l.MoveToFront(p)
		p = pnext
	}
	return l
}

// 按照排序函数来排序列表，排序函数 f 为 nil 时使用默认的排序函数
func (l *List) Sort(f CompareFunc) *List {
	sortfunc := f
	if sortfunc == nil {
		sortfunc = CompareDefaultFunc
	}
	for i := 0; i < l.Len(); i++ {
		j := 0
		now := l.Front()
		for p := l.Front(); p != nil && j < l.Len()-i; p = p.Next() {
			if sortfunc(p.Value, now.Value) {
				now = p
			}
			j++
		}
		l.MoveToBack(now)
	}
	return l
}

// 将列表拆成两个列表返回，一个包含前面 N 个元素，另一个包含剩下的元素
func (l *List) Split(N int) (*List, *List) {
	l1 := New()
	l2 := New()
	j := 0
	for p := l.Front(); p != nil; p = p.Next() {
		if j < N {
			l1.PushBack(p.Value)
		} else {
			l2.PushBack(p.Value)
		}
		j++
	}
	return l1, l2
}

// 将列表拆成两个列表返回
// 从头到尾依次复制满足条件的元素到第一个列表，直到遇到不满足条件的元素为止，剩下的复制到第二列表
func (l *List) SplitWith(f FilterFunc) (*List, *List) {
	l1 := New()
	l2 := New()
	pred := true
	for p := l.Front(); p != nil; p = p.Next() {
		if pred && f(p.Value) {
			l1.PushBack(p.Value)
		} else {
			pred = false
			l2.PushBack(p.Value)
		}
	}
	return l1, l2
}

// 返回一个从 Len 开始，个数为 Len 的子列表。
func (l *List) Sublist(Start int, Len int) *List {
	l1 := New()
	j := 0
	for p := l.Front(); p != nil; p = p.Next() {
		if j >= Start && j < Start+Len {
			l1.PushBack(p.Value)
		}
		j++
	}
	return l1
}

// 删除列表在另一列表里出现的元素
func (l *List) Subtract(l2 *List) *List {
	for p := l2.Front(); p != nil; p = p.Next() {
		l.Delete(p.Value)
	}
	return l
}

// 计算列表里每个元素的总和
func (l *List) Sum() int {
	acc := 0
	for p := l.Front(); p != nil; p = p.Next() {
		v, ok2 := p.Value.(int)
		if !ok2 {
			v = 0
			fmt.Println("lists Sum error: element is not int")
		}
		acc += v
	}
	return acc
}

// 从头到尾依次保留满足条件的元素，直到遇到不满足条件的元素为止。
func (l *List) TakeWhile(f FilterFunc) *List {
	pred := true
	for p := l.Front(); p != nil; {
		pnext := p.Next()
		if !pred || !f(p.Value) {
			l.Remove(p)
			pred = false
		}
		p = pnext
	}
	return l
}

// 对列表进行去重处理
func (l *List) Unique() *List {
	for p := l.Front(); p != nil; p = p.Next() {
		for pnext := p.Next(); pnext != nil; {
			pnextnext := pnext.Next()
			if p.Value == pnext.Value {
				l.Remove(pnext)
			}
			pnext = pnextnext
		}
	}
	return l
}
